今天來看兩個有趣的題目吧！

Exercise 23: Leetcode 174 - Dungeon Game

題目連結

https://leetcode.com/problems/dungeon-game

題目敘述

給你一個網格（grid），每一個格子裡面都有一個數字，代表國王踩上去血量的變化（負者扣血、正者回血。）國王血量沒有上限，但是一旦歸零就會死掉。請問國王要從左上角一路踩到右下角，中間每一步只能向右或向下的情形裡，一開始至少需要多少整數血量才不會半途死掉？

解題思考

如果一開始固定了國王了血量 X，那麼就可以從左上角開始，每走一格考慮前一步是從左邊來、或從上面來，在該格子紀錄下抵達該格目前可能的最大血量。這麼一來我們得到一個 O(MN log C) 時間的動態規劃，其中 C 指的是二分搜尋 X 這個血量的最大數值。

換個方向，換個腦袋

如果從右下角做回來，我們可以定義 dp(i, j) 為「從 (i, j) 這格出發，依序往右或往下走，活著到達右下角的格子時最小的初始血量」。這狀態要怎轉移呢？顯然第一步可以往右或往下。往右的話會要求至少達到 dp(i, j+1) 的血量，往下則是要求達到 dp(i+1, j) 的血量。我們定義前者數值為 R (Right)，後者數值為 D (Down)。如果這格是補血正值 P，那一開始必須達到 min(R, D) - P，或是至少有 1 滴血才行，因此此時可以把遞迴關係寫成 dp(i, j) = max(1, min(R, D) - P)。如果這格是扣血負值 Q，那麼一開始就必須達到 min(R, D) - Q 這麼多血才夠存活，這個遞迴關係寫起來是一樣的！

所以不知不覺就得到 O(MN) 時間的動態規劃演算法了！

參考程式碼 (Python3)

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        INF = sys.maxsize
        dp = [[INF for _ in row] for row in dungeon]
        rows, cols = len(dungeon), len(dungeon[0])
        dp[-1][-1] = max(1, 1 - dungeon[-1][-1])
        for i in range(rows-1, -1, -1):
            for j in range(cols-1, -1, -1):
                if j < cols-1:
                    dp[i][j] = min(dp[i][j], dp[i][j+1] - dungeon[i][j])
                if i < rows-1:
                    dp[i][j] = min(dp[i][j], dp[i+1][j] - dungeon[i][j])
                if dp[i][j] <= 0:
                    dp[i][j] = 1
        return dp[0][0]

Exercise 24: Leetcode 887 - Super Egg Drop

題目連結

https://leetcode.com/problems/super-egg-drop/

題目敘述

你有 K 顆一模一樣的雞蛋，還有一座高達 N 層的摩天大樓。已知這些雞蛋都有一個碎裂點：存在某個整數樓層 L，使得在不超過 L 的地方往下丟雞蛋，雞蛋完全不會受損、可以回收繼續使用。從 L+1 或更高樓層往下丟，則會讓雞蛋直接破掉，無法繼續使用。

每一次實驗，都可以選一個樓層，在還有雞蛋的情況下丟雞蛋進行測試（但遺憾的是破掉的話這顆雞蛋就沒了！）請問在最壞情形下，你至少要進行幾次實驗，才能跟夜神月一樣保證找到 L 呢？

解題思考

第一個想法很簡單呀：就看看第一次測試的時候要挑哪一個樓層丟雞蛋。假設我們選第 H 樓，那麼有兩種情形：碎掉的話那可能的 L 值便縮小到 0~H-1 之間，相當於我們回答一個高度為 H-1層樓、只有K-1顆雞蛋可用的丟雞蛋問題。如果沒碎掉的話，那可能的 L值便縮小到 H~N 之間，相當於我們回答一個高度為 N-H層樓、仍有K顆雞蛋可用的丟雞蛋問題。

太好啦！那我們就可以用 (K, N) 當作狀態、寫出遞迴式：

遞迴中止條件當然就是只有一顆蛋的情形啦～顯然得築層往上丟，如果跨層丟不小心破掉了，就沒蛋可測了，找不出正確的 L 值！所以 dp(1, N) = N，最壞情形下得測試 N 次。

這樣算起來——總共有 O(KN) 個狀態，計算每一個狀態得花 O(N) 的時間，好像加起來是 O(KN^2) 欸，非常可怕。好加在，我們可以透過不小心的突發奇想，發現其實 dp(K, 1), ..., dp(K, N) 應該得要是個遞增數列齁——樓層越高，最壞情況下要測試的次數當然得越多。所以對於這個取 max 的動作，一邊是個隨 h 增加而增加的函數、另一邊是隨 h 增加而減小的函數。要找出真正的 min max 我們只要對 h 二分搜尋就可以了啊！

因此時間複雜度可以作到 O(KN log N)，很棒吧！

參考程式碼 (Python3)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = {}
        def search(K, N):
            if K == 1:
                return N
            if K > N:
                return search(N, N)
            if dp.get((K, N)) != None:
                return dp[(K, N)]
            l, r = 1, N
            ans = sys.maxsize
            while l <= r:
                m = (l + r) // 2
                broken = search(K-1, m-1)
                safe = search(K, N-m)
                ans = min(ans, max(broken, safe) + 1)
                if broken <= safe:
                    l = m + 1
                else:
                    r = m - 1
            dp[(K, N)] = ans
            return ans
        return search(K, N)

換個研究方向，老師我想畢業

還記得今天的主題是什麼嗎？就是要把二分搜尋法省掉！

事實上，我們如果換個方向思考：如果我們只允許進行 D 次實驗，請問能夠負擔的最高樓層是多少呢？這個想法意外地可以推導出乾淨的遞迴式子：我們定義 f(K, D) 代表使用 K 顆雞蛋、至多進行 D 次實驗時，能夠在最壞情況下準確測出 L 的最高樓層數是多少層樓。

如果第一次實驗從 h 層樓丟下來，如果雞蛋破掉了，那麼這個 h 層樓不能超過被剩下 D-1 次實驗能夠推論出的樓層數量、加1 (因為頂樓 h 測過了)，也就是 f(K-1, D-1)+1 層樓。如果雞蛋沒破，那麼我們把 h 層當作不會破掉的「樓地板」往上測試，最高可以測到 h + f(K, D-1) 層樓啊。顯然此時 h 越大越好，選最大的 h = f(K-1, D-1) 就行了。因此我們得到：

給定 N 要怎麼找出最好的 D 呢？當然就是找最小且滿足 f(K, D) ≥ N 的那個 D 呀！掃一遍就知道了～這個時間複雜度是 O(KD)，顯然 D 不需要超過 N，因此這個時間複雜度就是 O(KN)。把二分搜尋法的時間省下來了，很棒吧！

參考程式碼 (Python3)

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        f = [[0] * (N+1) for _ in range(K+1)]
        for h in range(1, N+1):
            f[1][h] = h
        for k in range(2, K+1):
            for d in range(1, N+1):
                f[k][d] = 1 + f[k-1][d-1] + f[k][d-1]
        for d in range(1, N+1):
            if f[K][d] >= N:
                return d
        return N

如果您有相關的動態規劃例題，也歡迎提出討論互相交流唷～